﻿#include<iostream>
#include<vector>
using namespace std;
//
//int main()
//{
//
//	string str("Hello Bit.");
//
//	str.reserve(111);
//
//	str.resize(5);
//
//	str.reserve(50);
//
//	cout << str.size() << ":" << str.capacity() << endl;
//
//	return 0;
//
//}
//class Solution {
//public:
//    bool isPalindrome(string s) {
//
//        int i = 0;
//        while (i < s.size())
//        {
//            if ('A' <= s[i] && s[i] < 'Z' || 'a' <= s[i] && s[i] < 'z' || '0' <= s[i] && s[i] < '9')
//            {
//                if ('A' <= s[i] && s[i] < 'Z')
//                {
//                    s[i] += 32;
//                }
//                i++;
//            }
//            else {
//                s.erase(i, 1);
//            }
//        }
//        int left = 0;
//        int right = s.size() - 1;
//        while (s[left] == s[right])
//        {
//            left++;
//            right--;
//        }
//        if (left > right)
//            return true;
//        return false;
//    }
//};
//class Solution {
//public:
//    void reverse(string& s, int begin, int end)
//    {
//        while (begin < end)
//        {
//            swap(s[begin++], s[end--]);
//        }
//    }
//    string reverseStr(string s, int k) {
//        int begin = 0;
//        int end = 0;
//        while (end < s.size())
//        {
//            end++;
//            if (end - begin + 1 == 2*k)
//            {
//                reverse(s, begin, begin + k - 1);
//                begin = end = end + 1;
//            }
//
//        }
//        if (end - begin + 1 < k)
//        {
//            reverse(s, begin, end);
//        }
//        else
//        {
//            reverse(s, begin, begin + k - 1);
//        }
//        return s;
//    }
//};
//int main()
//{
//	string s1("abcd");
//	reverse(s1.begin()+1, s1.end()-1);
//	return 0;
//}
//class Solution {
//public:
//    string addStrings(string num1, string num2) {
//        int i1 = num1.length() - 1;
//        int i2 = num2.length() - 1;
//        int carry = 0;
//        string ret;
//        while (i1 >= 0 || i2 >= 0)
//        {
//            int n1 = i1 >= 0 ? num1[i1] - '0' : 0;
//            int n2 = i2 >= 0 ? num2[i2] - '0' : 0;
//            int sum = n1 + n2 + carry;
//            ret += sum % 10 + '0';
//            carry = sum / 10;
//            i1--;
//            i2--;
//        }
//        if (carry == 1)
//            ret += '1';
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//    string son(string& num, int n2)
//    {
//        string ret;
//        int carry = 0;
//        int i1 = num.size() - 1;
//        while (i1 >= 0)
//        {
//            int n1 = num[i1--]-'0';
//            int mul = n2 * n1 + carry;
//            carry = mul / 10;
//            ret += mul % 10+'0';
//        }
//        if (carry != 0)
//            ret += carry+'0';
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//    string multiply(string num1, string num2) {
//        string ret("0");
//        int i2 = num2.size() - 1;
//        int n2 = num2[i2] - '0';
//        //相乘
//        while (i2 >= 0)
//        {
//            //每位相乘
//            string tmp = son(num1, n2);
//            for (int i = 0;i < num2.size() - i2 - 1;i++)
//            {
//                tmp += '0';
//            }
//            cout << tmp << endl;
//            ret = addStrings(tmp, ret);
//            //下一位
//            if (i2 == 0)
//                break;
//            n2 = num2[--i2] - '0';
//        }
//        return ret;
//    }
//};
//int main()
//{
//    vector<vector<int>> triangle(3);
//
//    Solution s1;
//    string s2("0");
//    string s("0");
//    if (s2 == s)
//    {
//
//    }
//    string s3("9");
//
//    s1.multiply(s2, s3);
//    return 0;
//}
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param numbers int整型vector
//     * @return int整型
//     */
//    int MoreThanHalfNum_Solution(vector<int>& numbers) {
//        // write code here
//        int arr[10001] = { 0 };
//        for (auto i : numbers)
//        {
//            arr[i]++;
//        }
//        for (int i = 0;i < 10001;i++)
//        {
//            if (arr[i] > numbers.size() / 2)
//                return i;
//        }
//
//    }
//};
//int main()
//{
//    int arr[] = { 1,2,3,2,2,2,5,4,2 };
//    vector<int> i(arr, arr + sizeof(arr) / sizeof(int));
//    Solution s;
//    s.MoreThanHalfNum_Solution(i);
//
//
//    return 0;
//}
//void Fuc(int& v)
//{
//
//}
//int main()
//{
//	int a = 1;
//	int& v = a;
//	Fuc(v);
//	return 0;
//
//#include<vector>
//#include<vector>
//class Solution {
//    string relevant[10] = { " "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//
//public:
//
//    void recursion(string& digits, int deep, vector<string>& ret, string tmp, string* relevant) {
//        if (deep == digits.size())
//        {
//            ret.push_back(tmp);
//
//        }
//        for (int i = 0;i < relevant[digits[deep]-'0'].size(); i++)
//        {
//            recursion(digits, deep + 1, ret, tmp + relevant[digits[deep]-'0'][i], relevant);
//        }
//    }
//    vector<string> letterCombinations(string digits) {
//        vector<string> ret;
//
//        recursion(digits, 0, ret, " ", relevant);
//        return ret;
//    }
//};
//
//int main()
//{
//    string digits = "3";
//    Solution s;
//    s.letterCombinations(digits);
//    return 0;
//}
//class Time
//{
//public:
//	Time()
//	{
//		cout << "Time()" << endl;
//		
//	}
//private:
//	int _hour;
//	int _minute;
//	int _second;
//};
//class Date
//{
//private:
//	 基本类型(内置类型)
//	int _year;
//	int _month;
//	int _day;
//	 自定义类型
//	Time _t;
//};
//int main()
//{
//	Date d;
//	return 0;
//}
//#include<algorithm>
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        vector<int>::iterator it = nums.begin();
//        sort(it, nums.end());
//        while (it != nums.end())
//        {
//            int count = 0;
//            int num = *it;
//            while (*it == num && it != nums.end())
//            {
//                count++;
//            }
//            if (count == 1)
//                return num;
//        }
//        return 0;
//    }
//};
//int main()
//{
//    return 0;
//}
//class n
//{
//	void f();
//	void f()const;
//};
#include<stack>
#include<string>
class Solution {
public:

    int evalRPN(vector<string>& tokens) {
        for (auto& e : tokens)
        {
            if (e != "+" && e != "-" && e != "*" && e != "/")
                st.push( e);
            else
            {
                char symbol = e[0];
                int num1 = stoi(st.top());
                st.pop();
                int num2 = stoi(st.top());

                st.pop();
                if (symbol == '+')
                    st.push(to_string(num1 + num2));
                else if (symbol == '-')
                    st.push(to_string(num2 - num1));

                else if (symbol == '*')
                    st.push(to_string(num1 * num2));

                else
                    st.push(to_string(num2 / num1));

            }
        }
        return stoi(st.top());
    }
    stack<string> st;

};
int main()
{
    vector<string> tokens;
    //["2","1","+","3","*"]
    //["4","13","5","/","+"]
    tokens.push_back("4");
    tokens.push_back("13");
    tokens.push_back("5");
    tokens.push_back("/");
    tokens.push_back("+");
    Solution d1;
    d1.evalRPN(tokens);
	return 0;
}